function GRASP(vehicleCapacity, customersArray, distancesArray) {
	this._vehicleCapacity = vehicleCapacity;	//capacity of vehicle - given
	this._customersArray = customersArray;		//array of all customers - given
	this._distancesArray = distancesArray;		//array of pairs of distance - given
	
	this._customersArray[0]._served = true; 	//set depot as served
	this._N = customersArray.length; 			//number of customers - given
	this._Nserved = 1;							//number of customers served - calculated
	this._toursArray = [];						//array of tours being built - calculated
}

GRASP.prototype.MAXINT = 999999999;
GRASP.prototype.RESTRICTEDNUM = 2;

GRASP.prototype.calcSeedCustomers = function () {
	//Calculate the lower bound of number of vehicles
	var totalDemand = 0;
	for (var i = 1; i < this._N; i++) {
		totalDemand += this._customersArray[i]._demand;
	}
	var lowerBoundVehicle = Math.ceil(totalDemand/this._vehicleCapacity);
	//Construct the initial routes
	for (var i = 0; i < lowerBoundVehicle; i++) {
		//Search for unserved customer with maximum ( minimum distance to other served customers)
		var maxIndex = 0;
		var maxValue = 0;
		for (var j = 1; j < this._N; j++) {
			if (this._customersArray[j]._served == false){
				var minValue = this.MAXINT;
				for (var k = 1; k < this._N; k++) {
					if (this._customersArray[k]._served == true) {
						if (this._distancesArray[j][k] < minValue) { //how about this._distancesArray[k][j]?
							minValue = this._distancesArray[j][k];
						}
					}
				}
				if (minValue > maxValue) {
					maxValue = minValue;
					maxIndex = j;
				}
			}
		}
		this._Nserved += 1;
		this._customersArray[maxIndex]._served = true;
		this._toursArray.push([0,maxIndex,0]);
	}
}

GRASP.prototype.calcInsertionCost = function (n,i,j) {  //insertion cost for customer n between customer i and j
	return this._distancesArray[i][n] + this._distancesArray[n][j] - this._distancesArray[i][j];
}

GRASP.prototype.calcInsertionPosition = function (n,t) { //the position with least insertion cost for customer n  in a tour t
	//Starts ith assuming least insertion cost is at position 0
	var minIndex = 0;
	var minValue = this.calcInsertionCost(n,this._toursArray[t][0],this._toursArray[t][1]);
	//Go through all the remaining positions
	for (var i = 1; i < this._toursArray[t].length-1; i++) {
		var insertionCost = this.calcInsertionCost(n,this._toursArray[t][i],this._toursArray[t][i+1]);
		if (insertionCost < minValue) {
			minValue = insertionCost;
			minIndex = i;
		}
	}
	return [minIndex,minValue]; //[index in t, insertion cost]
}

GRASP.prototype.calcInsertionPriority = function (n) { //insertion priority for customer n
	//Starts ith assuming least insertion cost is at route 0
	var minIndex = 0;
	var minValue = [0,this.calcInsertionPosition(n,0)];
	var numberProcessed = 1;
	var insertionPriority = 0;
	//Go through all the remaining routes
	for (var t = 1; t < this._toursArray.length; t++) {
		var insertionPosition = this.calcInsertionPosition(n,t);
		if (insertionPosition[1] < minValue[1]) {
			minValue = insertionPosition;
			minIndex = t;
			insertionPriority += (minValue[1] - insertionPosition[1]) * numberProcessed;
		} else {
			insertionPriority += (insertionPosition[1] - minValue[1]);
		}
		numberProcessed += 1;
	}
	return [n,insertionPriority,minIndex,minValue[0]]; //[n, insertionPriority, tour index, position index in tour]
}

GRASP.prototype.calcNextCustomer = function () {
	var candidateList = [];
	for (var n = 0; n < this._N; n++) {
		if (this._customersArray[n]._served == false) {
			candidateList.push(this.calcInsertionPriority(n));
		}
	}
	candidateList.sort(function (a,b) {
		return b[1] - a[1];
	});
	
	var randomIndex = Math.floor( Math.random() * Math.min(this.RESTRICTEDNUM, candidateList.length) );
	var nextCustomer = candidateList[randomIndex];
	var nextCustomerIndex = nextCustomer[0];
	var nextTourIndex = nextCustomer[2];
	var nextTourPositionIndex = nextCustomer[3];
	
	this._Nserved += 1;
	this._customersArray[nextCustomerIndex]._served = true;
	this._toursArray[nextTourIndex].splice(nextTourPositionIndex+1, 0, nextCustomerIndex);
}

GRASP.prototype.exePlanning = function () {
	this.calcSeedCustomers();
	while (this._Nserved < this._N) {
		this.calcNextCustomer();
	}
	//return this._toursArray;
}
